翻訳と辞書 Words near each other ・ Read Township, Butler County, Nebraska ・ Read Township, Clayton County, Iowa ・ Read Yourself Raw ・ Read's Cavern ・ Read's Department Stores ・ Read's Drug Store ・ Read's Island ・ Read, Lancashire ・ Read, West Virginia ・ Read, Write, & Type! ・ Read-copy-update ・ Read-modify-write ・ Read-only ・ Read-only memory ・ Read-only right moving Turing machines ・ Read-only Turing machine ・ Read-through ・ Read-write memory ・ Read. (Dubai) ・ Read/write ・ Readability ・ Readability survey ・ Readability test ・ Readable ・ Readahead ・ Readalong ・ Readbourne ・ ReadCube ・ Readdle ・ Reade Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Read-only Turing machine ： ウィキペディア英語版 Read-only Turing machine A read-only Turing machine or Two-way deterministic finite-state automaton (2DFA) is class of models of computability that behave like a standard Turing machine and can move in both directions across input, except cannot write to its input tape. The machine in its bare form is equivalent to a Deterministic finite automaton in computational power, and therefore can only parse a regular language. == Theory == We define a standard Turing machine by the 9-tuple $M\; =\; (Q,\; \backslash Sigma,\; \backslash Gamma,\; \backslash vdash,\; \backslash \_,\; \backslash delta,\; s,\; t,\; r)$ where * $Q$ is a finite set of ''states''; * $\backslash Sigma$ is the finite set of the ''input alphabet''; * $\backslash Gamma$ is the finite ''tape alphabet''; * $\backslash vdash\; \backslash in\; \backslash Gamma\; -\; \backslash Sigma$ is the ''left endmarker''; * $\backslash \_\; \backslash in\; \backslash Gamma\; -\; \backslash Sigma$ is the ''blank symbol''; * $\backslash delta\; :\; Q\; \backslash times\; \backslash Gamma\; \backslash rightarrow\; Q\; \backslash times\; \backslash Gamma\; \backslash times\; \backslash$ is the ''transition function''; * $s\; \backslash in\; Q$ is the ''start state''; * $t\; \backslash in\; Q$ is the ''accept state''; * $r\; \backslash in\; Q,\; ~\; r\; \backslash ne\; t$ is the ''reject state''. So given initial state $q$ reading symbol $a$, we have a transition defined by $\backslash delta(q,a)=(q\_2,a\_2,d)$ which replaces $a$ with $a\_2$, transitions to state $q\_2$, and moves the "read head" in direction $d$ (left or right) to read the next input. In our 2DFA read-only machine, however, $a=a\_2$ always. This model is now equivalent to a DFA. The proof involves building a table which lists the result of backtracking with the control in any given state; at the start of the computation, this is simply the result of trying to move past the left endmarker in that state. On each rightward move, the table can be updated using the old table values and the character that was in the previous cell. Since the original head-control had some fixed number of states, and there is a fixed number of states in the tape alphabet, the table has fixed size, and can therefore be computed by another finite state machine. This machine, however, will never need to backtrack, and hence is a DFA. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Read-only Turing machine」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.